1. Field of the Invention
This invention pertains generally to image and video coding, and more particularly to tree adaptation for use in an adaptive entropy coding apparatus and method utilizing set partitioning in generalized hierarchical trees having directionality.
2. Description of Related Art
Entropy coding is an important constituent of image and video compression, which is usually in response to the steps of (1) transformation (and/or prediction), (2) quantization, and (3) entropy coding.
The following is described for the common JPEG entropy coding method, which stands for Joint Photographic Experts Group and is an ISO/IEC standard for a suite of computer image file compression techniques. A JPEG file is created by choosing from a range of compression qualities, or more accurately, from one of a number of compression algorithms. In converting an image through JPEG compression the target size or quality of the resultant image is specified to a quality level that approximates or is less than the original image. As the highest quality images result in the largest file, a trade-off is made between image quality and file size. The JPEG scheme according to the standard includes twenty-nine (29) distinct coding processes although a JPEG implementer may not use them all.
When performing entropy coding in JPEG, each 8×8 block is transformed using discrete cosine transforms (DCT), and the DCT coefficients are quantized, zig-zag scanned, and run-length coded. It will be recognized that run-length coding provides a way of encoding image data at lower rates by creating linear groups of identical pixels rather than storing the values of each pixel individually. Discrete Cosine Transformation (DCT) provides a mechanism for expressing any waveform as a weighted sum of cosines, and it is central to numerous forms of signal processing, in particular that of video compression.
FIG. 1A illustrates an example of zig-zag scanning in a 4×4 block, with coefficient locations shown in FIG. 1B. A number of drawbacks exist for performing entropy encoding according to this zig-zag pattern. In particular, there is (1) a lack of rate control mechanisms, while the (2) zig-zag scanning destroys the 2-D dependencies of the DCT coefficients.
It should be understood that the parameters used in quantization partially determine rate control, whereby different quantization parameters typically have to be tried to attain the desired file size.
Regarding the loss of 2-D dependency, it will be seen for example, that coefficient locations 2 and 6 in FIG. 1B are close in frequency spectrum as shown in the 4×4 block, yet they are not adjacent and are actually far from one another in response to the zig-zag scanning order shown in FIG. 1A.
Bit-plane based entropy coding is widely utilized in scalable image coding. In this process, transform coefficients are converted to the binary form, and coded from the most significant bit-plane (MSB) to the least significant bit-plane (LSB). During this process the encoding and decoding of lower bit-planes is based on a knowledge of higher bit-planes. The bitstream coding process can be stopped anywhere, at any depth of bit-planes, toward satisfying a given bitrate budget while providing a reasonably good reconstruction quality. The ability to stop at any point in the coding process is possible since the most important part of each coefficient (MSBs) has been already coded. This bitstream coding mechanism is known as embedded coding and provides good rate control.
Accordingly, a need exists for a method and apparatus for performing rate controllable encoding and decoding which has low complexity and high efficiency. These needs and others are met within the present invention, which overcomes the deficiencies of previously developed entropy-based image/video coding techniques.